\section{Case Study: Modeling P2P Communication Networks as CSTE Planning}
\label{sec:P2P}

As pointed out in \cite{Cushing07:ICAPS}, all temporal planning
domains in the recent International Planning Competitions are not
temporally expressive.  
%Qiang 3.15
The shortage of a sufficient number of temporally expressive planning domains (and hence CSTE domains) may become a hinder of future development of temporal planning. 
Introducing a new, sound and scalable CSTE planning domain is nontrivial.  A few
candidates for temporally expressive domains have been
proposed~\cite{Cushing07:ICAPS,Coles08}. Most of them, however, are
not truly representative of real-world problems. Aiming in part at
expanding our pool of temporal planning domains, we consider an important
P2P network problem described below.
%critical problem in networks, which is briefly discussed below.


In Peer-to-Peer (P2P) networks, each computer, called a peer, may
upload or download data from one another. In such a network, file
transmission is no longer limited by the bandwidth of a single
centralized server. Thus the overall throughput within the network
is significantly increased.  A large number of services have been
developed for P2P networks and more related distributed
systems~\cite{Subramanian05} keep coming out; it may potentially be
used in multi-core CPU architecture, a trend in current computer
architecture design. 


One critical issue in P2P networks is that a
substantial amount of inter-peer data communication traffic is
unnecessarily duplicated.
For those systems having consistent and intensive data sharing
between peers, communication latency is a potential bottleneck of
the overall network performance.  
%Qiang 3.15
%It is highly desirable, when
%designing a P2P network, to have not only a design plan, but also an
%optimal one to optimize the potential utility of the network.
Mechanisms in network design, particularly proxy caching (a.k.a.
gateway caching), have been proposed to reduce duplicated data
transmission. Making a good use of the proxy cache is critical for
optimizing data transmission.


The problems of duplicated communication traffic and communication
latency are intrinsically related.  To reduce or remove duplicated
communication and to effectively use proxy cache amount to
optimizing communication traffic. The main issue is to determine
each peer's actions at every time point, with the objective of
letting all peers get all data requested within the shortest
possible time. Due to its importance, optimizing communication
traffic in P2P networks has already attracted some
attention~\cite{Zhang09:SIGCOMM}. The problem, when casted as a
planning problem, is temporally expressive.
%R.Huang
%Later we will also discuss the reason why
%people have increasing interests in

We approach the problem of optimizing communication traffic in P2P
networks from the viewpoint of CSTE planning, and
use our CSTE planner to solve it. Our approach can
find plans with both the shortest  makespan and low total action costs.
There are some existing methods for general network planning.
For example, \cite{Rudenko2002} gives a domain-specific heuristic
planning algorithm. To the best of our knowledge,
our approach is the first general method that can handle both
temporally expressiveness and action costs.

\subsection{A CSTE planning model for P2P communication networks}
There are at least two different types of optimization in P2P networks.  
The first one is approached from the user's point of view: each individual user wants all the data needed within the shortest
possible time~\cite{Bhattacharya07}.  The other type is approached
from the point of view of a network service provider (such as an
Internet service provider (ISP)), who owns the network but does not
control individual peers.  The main concern of a service provider is
to reduce the overall communication load.

These two performance metrics are possibly conflicting. We
adopt performance metrics that lie in the middle of the
above mentioned two.  Under these metrics, the network owner knows
each peer's needs, and the objective is to minimize the overall
makespan for all the data delivery for all peers and minimize the
total communication loads caused by different
actions including serving and downloading.

The main constraint in this problem is that to satisfy a file request
from a peer $p_1$, the same file has to be offered by another peer $p_2$.
$p_1$ can execute the {\em download} action to get the file, when 1)
there is a route between $p_1$ and $p_2$, and 2) $p_2$ is {\em serving} the file
throughout the networks.  As such, these {\em serve} and {\em download} actions require 
concurrency for any valid plan.

In addition, the proxy cache, which stores local caching files, will guarantee that, when $p_2$ is {\em
serving} a file, any peer who is routed to $p_2$ can {\em download}
the file very quickly. The upload bandwidth of a peer is typically much
narrower than its download bandwidth.  Therefore, enforced by the
optimality goal, the more peers downloading this particular file, the
larger the whole network's throughput will be, which brings about a
shorter time span in a solution plan.

Below we specify the PDDL definition for a {\em serve} action.

%YC: add the definition of cost. check below
 %:cost (= ?cost (file-size ?f)*SERVE_RATE)
{
\begin{flushleft}
\begin{Verbatim}[frame=lines, samepage=true]
(:durative-action serve
 :parameters ( ?c - computer ?f - file )
 :duration (= ?duration (file-size ?f) )
 :condition( and
        (at start (free ?c) )
        (over all (not(free ?c )))
        (at start (saved ?c ?f))
        (over all (serving ?c ?f) ))
 :effect(and
        (at start  (not (free ?c )) )
        (at end    (free ?c ) )
        (at start  (serving ?c ?f) )
        (at end(not (serving ?c ?f) ))
        (increase (total-cost) (file-size ?f)*SERVE_RATE))
\end{Verbatim}
\end{flushleft}
}

 In the definition of the {\em serve} action, the processing time of a
file is proportional to its file size. We assume that by actively
sharing a file, the uploading peer uses up its uploading bandwidth.
That is, we assume that it cannot share another file simultaneously.
This assumption will not impose a real restriction as we can
introduce a time sharing scheme to extend the method we develop. A
predicate `serving' as one of the add-effects at the beginning
indicates that the peer is sharing a file.

When sharing a file from a peer, the connected route will guarantee
that any other peer can get this file in a constant time (because
download speed is much faster), as long as it is routed to the
uploading peer.

It is worthwhile to note that a good benchmark CSTE planning domain
must have, but not limited to, at least the following three
properties:
\begin{itemize}
\item Scalability in problem size (with respect to the makespan);

\item Controllability of the degree of concurrency;

\item Representativeness of a real-world application domain or
 problem, to be useful and for further development.
\end{itemize}

Being motivated by a real-world problem, the communication
optimization in P2P domain is scalable in problem size as an
arbitrary number of peers and files may participate. It is also
scalable in degree of concurrency as peers can be routed very
differently.


\subsection{Action costs in network communication}

Services for network communication used to be indistinctive. In other words, an
Internet service provider (or a general network server) does not
distinguish different types of services. As a result, two network
users always request exactly the same type of service.

Services become different now. The booming of service-oriented
architecture offers network communication new opportunities of
future developments. For instance, the widely used Service Level
Agreement (SLA) tries to make a layer over cloud computing or grid
computing infrastructures, such that a certain level of reliability
is always obtained, based on contracts between the service provider
and requesters. Even in a much simplified form, the agreement may
include, but not limited to, network bandwidth, loss rate, and various
other performance measurements.


Once services are distinguished by levels of quality, the service
providers consequently set different rates to charge the users
accordingly. As a result, service requesters may want to
minimize the cost brought up by the overall network communication
charges. In our P2P network model as an example, the network transmissions,
modeled as actions, have costs, in accordance to real-world quality
assured service models. When solving such a planning problem, we
want to minimize total action costs, in addition to minimizing the
makespan. In our current model, a `serve' action always has a higher
action cost than any `download' action does. 
This is because typically a `serve' action persists a longer time than a `download' action and uses more limited uploading bandwidth. 
When it is required to guarantee stability and availability, a peer computer would like to use a better network data link, it will have to incur higher charges by the network provider.


